The disclosure of the following priority application is herein incorporated by reference:
Japanese Patent Application No. 10-284531 filed Oct. 6, 1998
The disclosure of U.S. Pat. No. 5,594,554 is herein incorporated by reference.
1. Field of the Invention
The present invention relates to a data compression method and a recording medium with a data compression program for executing the data compression method recorded therein. More specifically, the present invention relates to technology through which conditions for quantization that are required to obtain a desired code volume are determined with a high degree of accuracy through a single trial.
2. Description of the Related Art
Processing such as image compression (e.g., JPEG compression) is performed on image data as a standard procedure in an electronic camera or a computer to record image data in a recording medium with a high degree of efficiency. Such image compression processing may be executed through the procedure described in (1)xcx9c(4) below, for instance.
(1) The image data are divided into pixel blocks each constituted of approximately 8xc3x978 pixels. Orthogonal transformation such as DCT (discrete cosine transformation) is performed on these pixel blocks to convert the image data to spatial frequency components.
(2) A standard quantization table that defines quantization increments corresponding to the individual spatial frequency components constituted of 8xc3x978 pixels is prepared. The standard quantization table is multiplied by a scale factor SF to obtain a quantization table that is to be used.
(3) Using the quantization table obtained as described above, the data that have undergone DCT are quantized.
(4) The quantized data are coded through variable-length coding, run-length coding or the like.
However, since the volume of information greatly varies among different sets of image data, it is extremely difficult to uniformly predict the code volume after compression. For this reason, it is necessary to follow the procedure in (1)xcx9c(4) described above many times while varying the value of the scale factor SF in order to perform the compression which results in a desired code volume (hereafter referred to as the xe2x80x9ctarget code volumexe2x80x9d). As a means for reducing the number of such trials, U.S. Pat. No. 5,594,554, the disclosure of which is herein incorporated by reference, discloses a method whereby a correct scale factor SF is determined based upon the minimum of two trial compressions.
FIG. 18 is a flowchart illustrating this method in the prior art. The following is an explanation of the method in the prior art, given along the flow of the steps in FIG. 18. First, in the method in the prior art, a first trial compression is performed on input image data. A scale factor SF1 used at this time and a code volume ACVdata1 after the compression are stored in memory (FIG. 18 S91).
Next, a second trial compression is performed on the input image data. A scale factor SF2 used at this time and a code volume ACVdata2 after the compression are stored in memory (FIG. 18 S92). The results thus obtained are incorporated in a relational expression representing the relationship between the scale factor SF and the code volume ACVdata to obtain;
First Relational Expression:
log(ACVdata1)=a*log(SF1)+bxe2x80x83xe2x80x83(1) 
and
Second Relational Expression:
log(ACVdata2)=a*log(SF2)+bxe2x80x83xe2x80x83(2). 
By solving expression 1 and expression 2 above, the two undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d in the relational expressions are ascertained (FIG. 18 S93). As a result, a relational expression that expresses in approximation the relationship between the scale factor SF and the code volume ACVdata is obtained for the input image data;
Relational Expression:
log(ACVdata)=a*log(SF)+bxe2x80x83xe2x80x83(3). 
By solving this relational expression 3 with a target code volume TCV substituted in it, an appropriate target scale factor NSF for achieving the target code volume TCV is calculated (FIG. 18 S94). Using this target scale factor NSF, the input image data are compressed again (FIG. 18 S95).
In the method in the prior art described above, at least two trial compressions must be executed to ascertain the two undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d. However, a further reduction in the number of trials is urgently required to support faster image compression and the like.
An object of the present invention is to provide a data compression method that makes it possible to obtain a target scale factor NSF through a single trial and a recording medium having a data compression program that makes it possible to implement the data compression method on a computer recorded therein.
FIG. 1 is a flowchart that illustrates the present invention. The following is an explanation of the present invention given in reference to FIG. 1.
In order to achieve the object described above, the data compression method according to the present invention comprises a quantization trial step (FIG. 1 S1, FIG. 4 S36, FIG. 9 S48, FIG. 12 S36, FIG. 14 S76) in which input data are quantized using an initial quantization table that is set in advance, a coding trial step (FIG. 1 S2, FIG. 4 S36, FIG. 9 S48, FIG. 12 S36, FIG. 14 S77) in which a code volume achieved when the data that have undergone quantization in the quantization trial step are coded is determined, a relationship ascertaining step (FIG. 1 S3 and S4, FIG. 4 S37, FIG. 9 S52, FIG. 12 S37, FIG. 14 S78 and S79) in which the scale factor in the initial quantization table and the code volume are substituted in xe2x80x9cthe relational expression representing the relationship between the code volume and the scale factorxe2x80x9d that includes two undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d to ascertain the undetermined parameters in the relational expression based upon xe2x80x9cthe relational expression after the substitutionxe2x80x9d and xe2x80x9cthe statistical relationship between the undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d obtained through a previous quantization operation,xe2x80x9d a scale factor determining step (FIG. 1 S5, FIG. 4 S38, FIG. 9 S53, FIG. 12 S38, FIG. 14 S80) in which a target scale factor that corresponds to the target code volume is determined by using the relational expression having the undetermined parameter ascertained in the relationship ascertaining step substituted therein, a quantization step (FIG. 1 S6 and S7, FIG. 4 S39, FIG. 9 S54, FIG. 12 S39, FIG. 14 S81 and S82) in which the input data are quantized using a quantization table that corresponds to the target scale factor determined in the scale factor determining step and a coding step (FIG. 1 S8, FIG. 4 S39, FIG. 9 S54, FIG. 12 S39, FIG. 14 S83) in which the data that have been quantized in the quantization step are coded.
The inventors of the present invention have discovered that, as demonstrated in the embodiments which are to be detailed later, there is a statistical relationship achieving a high degree of reproducibility between the two undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d. Thus, in the relationship ascertaining step in the present invention, this statistical relationship obtained through a previous quantization operation is utilized to ascertain the undetermined parameters. This substantially reduces the number of undetermined parameters in the relational expression explained above from 2 to 1.
Thus, it becomes possible to ascertain all the undetermined parameters in the relational expression by obtaining trial data of the input data (the scale factor, the code volume) at least once. Consequently, through the data compression method according to the present invention, the number of trials can be reduced compared to the number of trials required in the method in the prior art (at least 2), so that the quantity of calculation required in the data compression method and the length of time required for implementing the data compression method are reduced with a high degree of reliability.
In the data compression method described above, it is preferable that the relationship ascertaining step includes steps (1) and (2) described below.
(1) An area selection step (FIG. 9 S49) in which, with coordinate space whose axes are the scale factor and the code volume divided into a plurality of areas and the statistical relationship between the two undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d ascertained in advance for each of those areas, one of the plurality of areas is selected based upon the scale factor in the initial quantization table and the code volume determined in the coding trial step and
(2) An individual area relationship ascertaining step (FIG. 9 S50xcx9cS52) in which the undetermined parameters in the relational expression are ascertained by substituting the scale factor in the initial quantization table and the code volume determined in the coding trial step in the relational expression, based upon xe2x80x9cthe relational expression after the substitutionxe2x80x9d and xe2x80x9cthe statistical relationship in the area selected in the area selection step.xe2x80x9d
In the data compression method described above, the coordinate space whose axes are the scale factor and the code volume is divided into a plurality of areas and the parameters are ascertained for the individual areas. By determining the statistical relationship for each area in this manner, the accuracy and the reproducibility of the statistical relationship in the individual areas can be further improved. Thus, it is possible to ascertain the parameters with an even higher degree of accuracy.
In addition, in the area selection step, an area is selected based upon the scale factor and the code volume obtained during the trial stage. Thus, xe2x80x9cthe area selectionxe2x80x9d and xe2x80x9cthe parameter ascertainingxe2x80x9d can be executed at once using the results of a single trial to minimize the degree of increase in the calculation quantity and the required length of processing time that the processing of the individual areas entails.
Furthermore, during the scale factor determining step, it is preferable that the target code volume be varied in correspondence to the code volume determined in the coding trial step (FIG. 12 S60 and S61). By adopting such a data compression method, it is possible to avoid any degradation of information by increasing the target code volume when, for instance, the code volume obtained during the trial stage is relatively large and, consequently, high compression is difficult to achieve.
If, on the other hand, it is assumed that high compression of the input data is possible due to a small code volume obtained during the trial stage, the code volume can be reduced to an appropriate degree by lowering the target code volume. By varying the target code volume in conformance to the code volume obtained during the trial stage, it becomes possible to execute quantization that corresponds to the quality and the content of the input data in a flexible manner. In addition, such a change of the target code volume is executed based upon the code volume obtained during the trial stage. Consequently, it is possible to execute both xe2x80x9cthe change of target code volumexe2x80x9d and xe2x80x9cparameter ascertainingxe2x80x9d at once using the results of a single trial so that the degree to which the calculation quantity and the required length of processing time increase due to the change of the target code volume can be minimized.
Another data compression method comprises a quantization trial step (FIG. 1 S1, FIG. 4 S36, FIG. 9 S48, FIG. 12 S36) in which input data are quantized using an initial quantization table set in advance, a coding trial step in which a code volume ACVdata achieved when the data that have been quantized in the quantization trial step are coded is determined, a relationship ascertaining step (FIG. 1 S3 and S4, FIG. 4 S37, FIG. 9 S52, FIG. 12 S37) in which an unknown parameter xe2x80x9caxe2x80x9d is ascertained by calculating
a={log(ACVdata)xe2x88x92C2}/{log(ISF)+C1}, 
using the code volume ACVdata, the scale factor ISF in the initial quantization table and values C1 and C2 which are statistically determined through a previous quantization operation, a scale factor determining step (FIG. 1 S5, FIG. 4 S38, FIG. 9 S53, FIG. 12 S38) in which a target scale factor NSF is determined by calculating
NSF=(ACVdata/TCV)(xe2x88x921/a)*ISF, 
using the code volume ACVdata, the scale factor ISF in the initial quantization table and a target code volume TCV, a quantization step (FIG. 1 S6 and S7, FIG. 4 S39, FIG. 9 S54, FIG. 12 S39) in which the input data are quantized using a quantization table that corresponds to the target scale factor NSF determined in the scale factor determining step and a coding step (FIG. 1 S8, FIG. 4 S39, FIG. 9 S54, FIG. 12 S39) in which the data quantized in the quantization step are coded.
The data compression method described above is characterized in that the statistical relationship between the undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d is expressed through a linear expression, b=C1*a+C2. Thus, the statistical relationship can be stored in a simple manner using the two coefficients C1 and C2. In addition, since a simple linear expression is used when ascertaining the parameters, too, the calculation quantity and the required length of processing time can be reduced with ease.
Another data compression method comprises a quantization trial step (FIG. 16 S101) in which input data are quantized using an initial quantization table, a coding trial step (FIG. 16 S102) in which the code volume achieved when the data that have been quantized in the quantization trial step are coded is determined, a scale factor determining step (FIG. 16 S103 and S104) in which a target scale factor that corresponds to the code volume determined in the coding trial step is determined based upon the correlation between xe2x80x9cthe code volume resulting from quantization and coding of test data performed by using the initial quantization tablexe2x80x9d and xe2x80x9cthe target scale factor to be used to quantize the test data to achieve a target code volumexe2x80x9d that is ascertained and stored in advance, a quantization step (FIG. 16 S105) in which the input data are quantized using a quantization table corresponding to the target scale factor determined in the scale factor determining step and a coding step (FIG. 16 S106) in which the data quantized in the quantization step are coded.
As mentioned earlier, the inventors of the present invention have learned that there is a statistical relationship that achieves a high degree of reproducibility between the two undetermined parameters xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d. This means that xe2x80x9cthe code volume obtained during the trial stagexe2x80x9d and xe2x80x9cthe target scale factorxe2x80x9d correspond with each other on a one-to-one basis (in a univocal manner) with a high degree of probability. Thus, in the data compression method described above, the one-to-one correlation mentioned above is determined through testing and is stored as a preparation. Then, based upon this correlation, the corresponding target scale factor is directly or through interpolation obtained using the code volume obtained during the trial stage. Consequently, the target scale factor can be determined quickly without having to perform any arithmetic operation to calculate the undetermined parameters.
In the recording medium according to the present invention, a data compression program for executing the various data compression methods described above on a computer or an information processing apparatus is recorded. In addition, the data signal embodied in a carrier wave according to the present invention comprises the data compression program for executing the various data compression methods described above on a computer or an information processing apparatus. Furthermore, a data compression processing apparatus according to the present invention executes the various data compression methods explained above on input data. The electronic camera according to the present invention executes the various data compression methods on image data obtained through image capturing.